# 两数相加II: https://leetcode-cn.com/problems/add-two-numbers-ii/

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


# 这个是我不想尝试反转求的“错误代码”，想了很久，思路还是记录一下吧~
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        """
            首先链表不能反转， 如果可以反转， 那么首先反转后， 就变成 两数相加那道问题的求解了
            这道题困难在于：  当前位的和 = 当前位上两数之和 + 前一位的进位
            根据链表的指向， 我们是从 高位向低位计算， 逆过了这个求解过程。
            1. 初始化 n+1 长度的链表
            2. 计算每位的进位，先添加进去链表
            3. 计算当前位置和 % 10, 加上计算好的 上一位置的 进位, 此时还要看是否有进位，进到前一位， 求得当前位置的值 和 进位到下一位置的值

            思路失败~~~， 这样并好好求得正确的进位相加，得到错误的结果
        """
        # 1. 先计算两个链表的长度
        cur = l1
        n1 = 0
        while cur:
            cur = cur.next
            n1 += 1

        cur = l2 
        n2 = 0
        while cur:
            cur = cur.next
            n2 += 1
        
        n = max(n1, n2)

        # 创建 n + 1 长链表
        newHead = ListNode(0)
        cur = newHead
        for i in range(n):
            cur.next = ListNode(0)
            cur = cur.next

        # 2. 求进位
        p1, p2 = l1, l2
        p = newHead
        for i in range(n, 0, -1):
            # 1. 找到当前数字
            a = p1.val if i <= n1 else 0
            b = p2.val if i <= n2 else 0
            # 2. 进位
            carry  = (a + b) // 10
            p.val = carry
            p = p.next
            # 3. 更新指针后移
            if i <= n1: p1 = p1.next
            if i <= n2: p2 = p2.next
        
        # 3. 开始从高位往低为 计算和
        p1, p2 = l1, l2
        pre = newHead
        p = newHead.next
        for i in range(n, 0, -1):
            pass
        return newHead


# 下面是使用栈实现的， 不写反转的方法了
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        """
            若不能对原始链表进行翻转处理， 可以使用栈。
            使用两个栈，分别push() 进去各自节点， 一次pop()出来，就相当于反转了
        """
        stack1 = list()
        stack2 = list()
        cur = l1
        while cur:
            stack1.append(cur)
            cur = cur.next
        
        cur = l2
        while cur:
            stack2.append(cur)
            cur = cur.next
        
        # 使用头插法，这样不需要后序再反转一次链表了
        dumpy = ListNode()
        cur = dumpy.next
        carry = 0
        while stack1 or stack2:
            a = stack1.pop().val if stack1 else 0
            b = stack2.pop().val if stack2 else 0
            
            div = (a + b + carry) % 10
            carry = (a + b + carry) // 10

            # 头插法插入节点
            node = ListNode(div)
            node.next = dumpy.next
            dumpy.next = node

        # 最后carry不为0，新加节点
        if carry > 0:
            node = ListNode(carry)
            node.next = dumpy.next
            dumpy.next = node
        
        return dumpy.next



# 跟两数相加一样， 可以优化掉 外面判断的 carry
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        """
            只需要把 循环条件改一下，多加一个 carry(进位)
            while stack1 or stack2 or carry > 0:
            就可以省去最后单独对 carry的 判断了
        """
        stack1 = list()
        stack2 = list()
        cur = l1
        while cur:
            stack1.append(cur)
            cur = cur.next
        
        cur = l2
        while cur:
            stack2.append(cur)
            cur = cur.next
        
        # 使用头插法，这样不需要后序再反转一次链表了
        dumpy = ListNode()
        cur = dumpy.next
        carry = 0
        while stack1 or stack2 or carry > 0:
            a = stack1.pop().val if stack1 else 0
            b = stack2.pop().val if stack2 else 0
            
            div = (a + b + carry) % 10
            carry = (a + b + carry) // 10

            # 头插法插入节点
            node = ListNode(div)
            node.next = dumpy.next
            dumpy.next = node
        
        return dumpy.next